home *** CD-ROM | disk | FTP | other *** search
/ Oh!X 2001 Spring / Oh!X 2001 Spring Special CD-ROM (Japan).7z / Oh!X 2001 Spring Special CD-ROM (Japan) (Track 1).bin / PUZZLE / Puz02 / keiro_b.c < prev    next >
C/C++ Source or Header  |  2000-02-20  |  2KB  |  89 lines
  1. /*
  2.  * keiro_b.c : 幅優先探索の例題
  3.  *
  4.  */
  5. /*
  6.         1       3       5
  7.         Ｂ------Ｄ------Ｆ
  8.       ／│      │          
  9.   0 Ａ  │      │          
  10.       ＼│      │          
  11.         Ｃ------Ｅ------Ｇ
  12.         2       4       6
  13.  
  14.          経路図
  15.  
  16. */
  17. #include <stdio.h>
  18. #include <stdlib.h>
  19. #include <string.h>
  20.  
  21. #define NODE 7
  22. #define SIZE 64
  23.  
  24. /* 隣接リスト */
  25. const char adjacent[NODE][4] = {
  26.   1,  2, -1, -1,    /* A */
  27.   0,  2,  3, -1,    /* B */
  28.   0,  1,  4, -1,    /* C */
  29.   1,  4,  5, -1,    /* D */
  30.   2,  3,  6, -1,    /* E */
  31.   3, -1, -1, -1,    /* F */
  32.   4, -1, -1, -1,    /* G */
  33. };
  34.  
  35. /* Queue */
  36. char path[SIZE][NODE];
  37. char length[SIZE];
  38.  
  39. /* 経路の表示 */
  40. void print_path( int n, int goal )
  41. {
  42.   int i;
  43.   int len = length[n];
  44.   for( i = 0; i <= len; i++ ){
  45.     printf("%c ", path[n][i] + 'A' );
  46.   }
  47.   printf("%c\n", goal + 'A' );
  48. }
  49.  
  50. /* 幅優先探索 */
  51. void search( int start, int goal )
  52. {
  53.   int wc = 1, rc = 0;
  54.   /* 初期化 */
  55.   path[0][0] = start; /* スタート地点をセット */
  56.   length[0] = 0;
  57.   while( rc < wc ){
  58.     int len = length[rc];
  59.     int node = path[rc][len];
  60.     int i, n;
  61.     for( i = 0; (n = adjacent[node][i]) != -1; i++ ){
  62.       if( memchr( path[rc], n, len + 1 ) == NULL ){
  63.     if( n == goal ){
  64.       /* ゴールに到達 */
  65.       print_path( rc, goal );
  66.     } else {
  67.       /* 経路を進める */
  68.       memcpy( path[wc], path[rc], len + 1 );
  69.       path[wc][len + 1] = n;
  70.       length[wc] = len + 1;
  71.       wc++;
  72.     }
  73.       }
  74.     }
  75.     rc++;
  76.   }
  77.   printf("状態数 %d 個\n", wc );
  78. }
  79.  
  80. int main()
  81. {
  82.   search( 0, 6 );
  83.   return 0;
  84. }
  85.  
  86.  
  87. /* end of file */
  88.  
  89.